/**
 * https://leetcode-cn.com/problems/sum-of-left-leaves/
 * 左子叶之和
 * @param root 
 */
const sumOfLeftLeaves = (root: TreeNode | null): number => {
    if (root === null) return 0

    const stack: TreeNode[] = [];
    let ans = 0;

    /**
     * 判断节点是不是叶子节点
     * @param n 
     */
    const isLeaf = (n: TreeNode) => n.left !== null && n.right !== null;


    // 根节点入栈
    stack.push(root);
    // 只到栈为空
    while (stack.length > 0) {
        // 弹出节点
        const n = stack.shift()!;

        if (n.left !== null) {
            // 判断左孩子是不是叶子节点
            if (isLeaf(n.left)) {
                ans += n.left.val;
            } else {

                // 左孩子不是叶子节点, 加入栈中
                stack.push(n.left);
            }
        }

        if (n.right !== null) {
            // 右孩子压入栈中
            stack.push(n.right);
        }
    }

    return ans

};


// 递归
const sumOfLeftLeaves2 = (root: TreeNode | null): number => {
    let ans = 0

    /**
     * 求左右的左子叶值合
     * @param n 
     */
    const sum = (n: TreeNode | null, isLeft: boolean = false) => {
        if (n === null) return

        // 是叶子节点并且左右为空
        if (n.left == null && n.right === null && isLeft) {
            ans += n.val
            return
        }

        // 左孩子
        sum(n.left, true);

        // 右孩子
        sum(n.right);
    }

    sum(root)

    return ans
};